package com.sam.book;

/**
 * Created by samwang on 2018/1/7.
 */
public class BinaryHeap<T extends Comparable<? super T>> {

    public static final int DEFAULT_CAPACITY = 10;
    private int currentSize;
    private T[] array;


    public BinaryHeap() {

    }

    public BinaryHeap(int capacity) {

    }

    public BinaryHeap(T[] array) {
        currentSize = array.length;
        this.array = (T[]) new Comparable[(currentSize + 2) * 11 / 10];

        int i = 1;
        for (T t : array) {
            array[i++] = t;
        }

        buildHeap();

    }

    public void insert(T t) {
        if (currentSize == array.length - 1) {//位置0空出来。。。？？
            enlargeArray(array.length * 2 + 1);
        }
        //percolate up
        int hole = ++currentSize;//空节点所在位置
        for (array[0] = t; t.compareTo(array[hole / 2]) < 0; hole /= 2) {//array[0] = t使得如果t是最小的，到1即树根时，循环终止
            array[hole] = array[hole / 2];//将空节点的父节点放于空节点位置，避免交换需要3次赋值
        }
        array[hole] = t;//最后将插入的节点置于空节点上

    }

    public T findMin() {
        return array[1];
    }

    public T deleteMin() {
        if (isEmpty()) {
            return null;
        }

        T t = findMin();
        array[1] = array[currentSize--];//把最后一个节点放在根节点沉下去。

        percolateDown(1);
        return t;

    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    public void makeEmpty() {
        currentSize = 0;
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
    }

    private void percolateDown(int hole) {
        int child;
        T t = array[hole];//将要下滤的节点保存，然后此位置当作空节点下滤
        for (; hole * 2 <= currentSize; hole = child) {
            child = hole * 2;
            if (child != currentSize && array[child + 1].compareTo(array[child]) < 0) {//左子节点不是最后（有两个子节点时） && 左儿子比较大
                child++;//则++,使后面t与右儿子（即较小的儿子比较）
            }
            if (array[child].compareTo(t) < 0) {//如果两个儿子，child是较小的，如果一个儿子child为左儿子
                array[hole] = array[child];//如果较小的儿子比t小，则该儿子与t（空节点）互换
            } else {
                break;//如果较小的已经比t大，则t下滤完成，这个位置就是要下滤的节点最终到达的位置
            }
        }

        array[hole] = t;//下滤完成，将要下滤的元素放到它该放的位置。
    }

    /**
     * 将array中的值构建成堆
     */
    private void buildHeap() {
        for (int i = currentSize / 2; i > 0; i--) {
            percolateDown(i);//从树的一半往根处循环 开始下滤
        }

    }

    private void enlargeArray(int newSize) {

    }

}
